package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         128,
		Discription: "最长连续数字的序列（下标可以不连续，下标顺序也无所谓）",
		Level:       2,
		Labels: map[string]int{
			"哈希表": 1,
		},
	})
}

//O（3n）
func LongestConsecutive(nums []int) int {
	//O(n)
	valMap := make(map[int]bool, 0)
	for _, val := range nums {
		valMap[val] = true
	}

	//O(2n)，每个元素最多被遍历两次，一次是正常的遍历，还一次是算长度时的遍历
	maxLength := 0
	for val := range valMap {
		//只有当val不作为一个序列的起点时才计算长度
		if valMap[val-1] {
			continue
		}

		length := 1
		for valMap[val+1] {
			length++
			val++
		}
		if length > maxLength {
			maxLength = length
		}

	}

	return maxLength
}
